#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<vector<int>> maxMoney(vector<vector<int>> &foods, int maxCarry){
    vector<int> array(maxCarry + 1, 0);
    vector<vector<int>> money{foods.size(), array};

    for(int i = 1; i < foods.size(); ++i){//遍历行
        for(int j = 1; j <= maxCarry; ++j){//遍历列
            int price = foods[i][0]; 
            int weight = foods[i][1];
    
            if(weight > j){
                money[i][j] = money[i-1][j];
            }
            else{
                money[i][j] = max(money[i-1][j], price + money[i-1][j-weight]);
            }
        }
    }

    return money;
}

//带⾛哪些⾷物，得到的钱数才最多
vector<vector<int>> getfoods(const vector<vector<int>> &money, const vector<vector<int>> &foods){
    vector<vector<int>> result;
    
    for(int row = money.size() - 1; row > 0; --row){
        int weight = foods[row][1];
        for(int col = money.front().size() - 1; col > 0; --col){
            if(money[row][col] != money[row - 1][col]){
                result.push_back(foods[row]);
                col -= weight;
                row -= 1;
            }
            else{
                result.push_back(foods[row - 1]);
                return result;
            }
        }
    }
    return result;
}
int main(int argc, char const *argv[])
{
    vector<vector<int>> foods{
        {0, 0},
        {1, 2},
        {4, 3},
        {5, 6},
        {6, 7}
    };
    int maxCarry = 10;
    vector<vector<int>> money = maxMoney(foods, maxCarry);
    cout << money.back().back() << endl;
    vector<vector<int>> getfoods1 = getfoods(money, foods);
    
    for(int i = 0; i < getfoods1.size(); ++i){
        for(int j = 0; j < getfoods1.front().size(); ++j){
            cout << getfoods1[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}
